面试题 17.09.第 k 个数

1、题干

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

示例 1:

输入: k = 5

输出: 9

1、解题思路

一开始没想到动态规划、三指针、步进法这些方案，看了题解还是觉得这些规律或方案有点难想到。我的第一反应是：这个问题好像可以用BFS+Set去重来解决。

1.1、转换思路

根据这个方向，实际上可以把问题转换成：已知一棵树的根是1，第一层节点是根节点与 3、5、7相乘的结果，第二层节点是第一层节点与 3、5、7相乘的结果，以此类推； 求这棵树中按广度遍历的第k个子节点的值。于是写下了这段代码：

var getKthMagicNumber = function(k) {
    let nums = [1];

    while (nums.length) {
        const set = new Set();

        for (let i = 0; i < nums.length; i++) {
            k--;
            if (!k) return nums[i];
            set.add(3 * nums[i]);
            set.add(5 * nums[i]);
            set.add(7 * nums[i]);
        }

        nums = [...set];
    }
};

1.2、测试出错

写完之后测试出错，是因为忽略了一个很重要的条件：按顺序排列。在上述代码中用于遍历树的 nums 代表的是每一层节点，它始终是单调递增的。虽然每一层节点都单调递增，但是随着层数增加，下一层的节点却有可能小于上一层节点。

1.3、解决问题

要解决这个问题也不难，只要把所有节点都放入 nums 中，并且保证它的单调性就OK了。

1.4、整体方案

因此，使用BFS + Set去重 + 单调栈的方式就能解出这道题，问题的关键点有以下3个：

• 使用非递归的BFS方式进行遍历
• 使用Set去除重复的数字
• 使用单调栈保证数字升序排列

2、代码

var getKthMagicNumber = function (k) {
    const nums = [1];
    const set = new Set();

    for (let i = 0; i < k; i++) {
        if (i + 1 === k) return nums[i];
        const arr = [3 * nums[i], 5 * nums[i], 7 * nums[i]];

        arr.forEach(n => {
            if (set.has(n)) return;
            set.add(n);

            if (n >= nums[nums.length - 1]) return nums.push(n);

            // 以上代码是常规逻辑：BFS + Set去重 
            // 以下代码是为了保证 nums 的单调性
            const arr = [];
            while (n < nums[nums.length - 1]) {
                arr.unshift(nums.pop());
            }
            nums.push(n, ...arr);
        });
    }
};